home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / tree_collection.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  2.6 KB  |  69 lines
  1. {\magonebf 3.11 Dynamic collections of trees  (tree\_collection) }
  2.  
  3. \decl tree\_collection I
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $D$ of the parameterized data type \name\ is a 
  8. collection of vertex disjoint rooted trees, each of whose vertices has a 
  9. double-valued cost and contains an information of type $I$, called the 
  10. information type of $D$.
  11.  
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16. \create D {}
  17.  
  18. creates an instance \var\ of type \name, initialized with the empty collection.
  19.  
  20.  
  21.  
  22. \bigskip
  23. {\bf 3. Operations}
  24.  
  25. \medskip
  26. \+\cleartabs & \hskip 2truecm & \hskip 5truecm &\cr
  27. \+\op d\_vertex   maketree {I\ x}  
  28.                              {Adds a new tree to $D$ containing a single }
  29. \+\nop                       {vertex $v$ with cost zero and information $x$,}
  30. \+\nop                       {and returns $v$.} 
  31. \smallskip 
  32. \+\op I           inf {d\_vertex\ v} 
  33.                              {Returns the information of vertex $v$.}
  34. \smallskip
  35. \+\op d\_vertex   findroot {d\_vertex\ v} 
  36.                              {Returns the root of the tree containing $v$.}
  37. \smallskip
  38. \+\op d\_vertex   findcost {d\_vertex\ v,\ double\&\ x} {}
  39. \+\nop                       {Sets $x$ to the minimum cost of a vertex on the}
  40. \+\nop                       {tree path from $v$ to findroot($v$) and returns}
  41. \+\nop                       {the last vertex (closest to the root) on this }
  42. \+\nop                       {path of cost $x$.}
  43. \smallskip
  44. \+\op void        addcost {d\_vertex\ v,\ double\ x} {}
  45. \+\nop                       {Adds double number $x$ to the cost of every vertex}
  46. \+\nop                       {on the tree path from $v$ to findroot($v$)}.                                 
  47. \smallskip
  48. \+\op void        link {d\_vertex\ v,\ d\_vertex\ w} {}
  49. \+\nop                   {Combines the trees containing vertices $v$ and $w$}
  50. \+\nop                   {by adding the edge $(v,w)$. (We regard tree }
  51. \+\nop                   {edges as directed from child to parent.) }
  52. \+\nop                   {\precond $v$ and $w$ are in different trees }
  53. \+\nop                   {and $v$ is a root.}
  54. \smallskip
  55. \+\op void        cut {d\_vertex\ v}
  56.                             {Divides the tree containing vertex $v$ into}
  57. \+\nop                      {two trees by deleting the edge out of $v$.}
  58. \+\nop                      {\precond $v$ is not a tree root.}
  59.                                                                       
  60. \bigskip
  61. {\bf 4. Implementation}
  62.  
  63. Dynamic collections of trees are implemented by partitioning the trees
  64. into vertex disjoint paths and representing each path by a self-adjusting
  65. binary tree (see [T83]). All operations take amortized time $O(\log n)$
  66. where $n$ is the number of maketree operations.
  67.  
  68.  
  69.